package com.itcast.demo.simple;

import java.util.HashMap;
import java.util.Map;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
 * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
 *
 * @author zheng.zhang
 */
public class Test3 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 4, 2, 5, 2, 3};
        Test3 test3 = new Test3();
        System.out.println(test3.moreThanHalfNumSolution2(arr));
        System.out.println(test3.getCount());
    }

    public int getCount() {
        int count = 1;
        for (int i = 0; i <= 100; i++) {
            count = count++;
            //count++;
        }
        return count;
    }

    /**
     * 数组中超过一般的数字
     *
     * @param array 数组
     * @return 数字
     */
    public int moreThanHalfNumSolution(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        Map<Integer, Integer> tempMap = new HashMap<>(array.length);
        for (int arr : array) {
            if (tempMap.containsKey(arr)) {
                tempMap.put(arr, tempMap.get(arr) + 1);
                continue;
            }
            tempMap.put(arr, 1);
        }
        int result = 0;
        int countTemp = 0;
        for (Integer i : tempMap.keySet()) {
            Integer count = tempMap.get(i);
            if (count > countTemp) {
                countTemp = count;
                result = i;
            }
        }
        return countTemp > array.length / 2 ? result : 0;
    }

    /**
     * 数组中超过一般的数字
     * 1, 2, 3, 2, 4, 2, 5, 2, 3
     *
     * @param array 数组
     * @return 数字
     */
    public int moreThanHalfNumSolution2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int count = 0;
        int win = 0;
        for (int i : array) {
            // 战场上没人
            if (count == 0) {
                win = i;
                count = 1;
            } else {
                if (win == i) {
                    // 同一阵营
                    count++;
                } else {
                    // 不同阵营
                    count--;
                }
            }
        }
        int resultCount = 0;
        for (int i : array) {
            if (i == win) {
                resultCount++;
            }
        }
        return resultCount > array.length / 2 ? win : 0;
    }
}
